package previous.Test_0214;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //单词搜索
    boolean[][] visit;
    int m,n,s;
    char[] word;
    public boolean exist(char[][] board, String _word) {
          //行数
        m=board.length;
          //列数
        n=board[0].length;
        visit=new boolean[m][n];
        word=_word.toCharArray();
        //寻找单词
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //如果有单词对应
                if (board[i][j]==word[0]) {
                    visit[i][j]=true;
                    //如果有
                   if( dfs(board,i,j,1)==true){
                       return true;
                   }
                   //恢复
                    visit[i][j]=false;
                }
            }
        }
        //如果全部遍历完都没有对应单词
        return false;
    }
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public boolean dfs(char[][] board,int i,int j,int pos){
        //递归出口
        if(pos==word.length){
            return true;
        }
        //上下左右匹配单词
        for (int k = 0; k < 4; k++) {
            int x=i+dx[k];
            int y=j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !visit[x][y] && board[x][y]==word[pos]){
                visit[x][y]=true;
               if( dfs(board,x,y,pos+1)==true){
                   return true;
               }
                visit[x][y]=false;
            }
        }
        return false;
    }
    //黄金矿工
    int m1,n1;
    boolean[][] vis;
    int path;
    public int getMaximumGold(int[][] grid) {
        m1=grid.length;
        n1=grid[0].length;
        vis=new boolean[m1][n1];
        for (int i = 0; i < m1; i++) {
            for (int j = 0; j < n1; j++) {
                if(grid[i][j]!=0){
                    vis[i][j]=true;
                    dfs(grid,i,j,grid[i][j]);
                    vis[i][j]=false;
                }
            }
        }
        return path;
    }
    int[] dx1={0,0,1,-1};
    int[] dy1={1,-1,0,0};
    public void dfs(int[][] grid,int i,int j,int ret){
        path=Math.max(ret,path);
        for (int k = 0; k < 4; k++) {
            int x=i+dx1[k];
            int y=j+dy1[k];
            if(x>=0 && x<m1 && y>=0 && y<n1 && !vis[x][y] && grid[x][y]!=0){
                vis[x][y]=true;
                ret+=grid[x][y];
                dfs(grid,x,y,ret);
                ret-=grid[x][y];
                vis[x][y]=false;
            }
        }
    }
    //不同路径
    int m2,n2;
    boolean[][] vis2;
    int count;
    int step;
    int ret;
    public int uniquePathsIII(int[][] grid) {
        m2=grid.length;
        n2=grid[0].length;
        vis2=new boolean[m2][n2];
        int zero=0;
        step=0;
        int bx=0;
        int by=0;
        for (int i = 0; i < m2; i++) {
            for (int j = 0; j < n2; j++) {
                if(grid[i][j]==0){
                    zero++;
                }
                if(grid[i][j]==1){
                    bx=i;
                    by=j;
                }
            }
        }
        step=zero+2;
        vis2[bx][by]=true;
        dfs1(grid,bx,by,1);
        return count;
    }
    int[] dx2={0,0,1,-1};
    int[] dy2={1,-1,0,0};
    public void dfs1(int[][] grid,int i,int j,int ret){
        if(grid[i][j]==2){
            if(ret==step) count++;
            return;
        }
        for (int k = 0; k < 4; k++) {
            int x=i+dx2[k];
            int y=j+dy2[k];
            if(x>=0 && x<m2 && y>=0 && y<n2 && grid[x][y]!=-1 && !vis2[x][y]){
                vis2[x][y]=true;
                dfs1(grid,x,y,ret+1);
                vis2[x][y]=false;
            }
        }
    }
    //图像渲染
    boolean[][] vis3;
    int m3,n3;
    int center;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
          m3=image.length;
          n3=image[0].length;
          center=image[sr][sc];
          if(center==color){
              return image;
          }
          dfs3(image,sr,sc,center,color);
          return image;
    }
    int[] dx3={0,0,1,-1};
    int[] dy3={1,-1,0,0};
    public void dfs3(int[][] image,int i,int j,int center,int color){
        image[i][j]=color;
        for (int k = 0; k < 4; k++) {
            int x=i+dx3[k];
            int y=j+dy3[k];
            if(x>=0 && x<m3 && y>=0 && y<n3 && image[x][y]==center){
                dfs3(image,x,y,center,color);
            }
        }
    }
    //岛屿数量
    int m4,n4;
    boolean[][] vis4;
    public int numIslands(char[][] grid) {
          m4=grid.length;
          n4=grid[0].length;
          int ret=0;
          vis4=new boolean[m4][n4];
        for (int i = 0; i < m4; i++) {
            for (int j = 0; j < n4; j++) {
                if(!vis4[i][j] && grid[i][j]=='1'){
                    ret++;
                    vis4[i][j]=true;
                    dfs4(grid,i,j);
                }
            }
        }
        return ret;
    }
    int[] dx4={0,0,1,-1};
    int[] dy4={1,-1,0,0};
    public void dfs4(char[][] grid,int i,int j){
        vis4[i][j]=true;
        for (int k = 0; k < 4; k++) {
            int x=i+dx4[k];
            int y=j+dy4[k];
            if(x>=0 && x<m4 && y>=0 && y<n4 && !vis4[x][y] && grid[x][y]=='1'){
                dfs4(grid,x,y);
            }
        }
    }
}
